Ascher et al, 23 IEEE Transactions on Computers, pages 1174-79, November 1974, describes machine implementable adaptive pattern matching in order to compress optically scanned documents for facsimile transmission or storage. In this regard, Ascher uses a stored program controlled machine in which he forms similarity classes, derives a class prototype, and achieves compression by encoding each character in the stream as the nearest class prototype.
In Ascher the digital images are segmented into dot pattern areas or sub-arrays of black-white pels. The patterns are sequentially grouped into classes according to a measure of their similarities such as Hamming distance. The first pattern put into a class is registered as the class prototype. As the process continues, each new segmented pattern is compared with the prototypes accumulated up to that point. If it matches any prototype, then the class index rather than the entire pattern, is recorded in the output data stream. This thereby increases the compression ratio. If no match is found, the full segmented pattern is recorded in the output stream and the pattern is also used to form a new class and prototype which are added to the available set.
Goddard et al, 22 IBM Technical Disclosure Bulletin, page 4429, March 1980, teaches the use of computer executed tree recognition followed by template comparison. That is, an input pattern is identified by way of a tree search of characters in the library. The search output is a tentative identification of the input character. The original character is then compared with the prototype indicated by the search. If the two characters match within some safe distance, then the identification is confirmed.
Casey, 22 IBM Technical Disclosure Bulletin, pages 1189-90, August 1979, describes a computer implementable method for constructing a decision tree used with an OCR algorithm. The method involves the estimation of picture element (PEL) statistics for each character type and the alteration of the OCR decision tree utilizes the statistics. Parenthetically, PELs assume either one of two color values, namely, black or white.
The aforementioned art suffers the disadvantage that most input patterns must be compared on a PEL by PEL basis with a large number of prototypes in order to find a match. This requires considerable computation time and further may require significant buffering where speed matching between information source and sink is required.